package leetcode.D100.T52;

import java.util.Arrays;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-25 22:27:28 星期五
 */
class Solution {

    // 基本照搬H51（N皇后）
    private int result = 0;

    public int totalNQueens(int n) {
        int[] col2row = new int[n];
        Arrays.fill(col2row, -1);
        int[] row2col = new int[n];
        dfs(col2row, row2col, 0);
        return result;
    }

    private void dfs(int[] col2row, int[] row2col, int row) {
        if (row == row2col.length) {
            result++;
            return;
        }
        for(int col=0; col<row2col.length; ++col) {
            if (valide(row, col, col2row, row2col)) {
                col2row[col] = row;
                row2col[row] = col;
                dfs(col2row, row2col, row+1);
                col2row[col] = -1;
            }
        }
    }

    private boolean valide(int row, int col, int[] col2row, int[] row2col) {
        if (col2row[col] >= 0)
            return false;
        for(int i=0; i<row; i++) {
            int j = row2col[i];
            if ((row-i) == Math.abs(col-j))
                return false;
        }
        return true;
    }
}
